package org.example.sort;

import java.math.BigInteger;
import java.util.*;

/**
 * 力扣--排序系列
 * @Author chaigq
 * @Date 2020/11/18 11:53 上午
 * @Version 1.0
 */
public class LeetCodeSort {

    /**
     * 给定一个整数数组 nums，返回区间和在 [lower, upper] 之间的个数，包含 lower 和 upper。
     * 区间和 S(i, j) 表示在 nums 中，位置从 i 到 j 的元素之和，包含 i 和 j (i ≤ j)。
     *
     *  说明:
     * 最直观的算法复杂度是 O(n2) ，请在此基础上优化你的算法。
     *
     *  示例:
     *
     *  输入: nums = [-2,5,-1], lower = -2, upper = 2,
     * 输出: 3
     * 解释: 3个区间分别是: [0,0], [2,2], [0,2]，它们表示的和分别为: -2, -1, 2。
     *
     *  Related Topics 排序 树状数组 线段树 二分查找 分治算法
     */
    // TODO 暴力求解
    public int countRangeSum(int[] nums, int lower, int upper) {
        int count = 0;
        for (int i = 0; i < nums.length; i ++){
            long sum = nums[i];
            for (int j = i + 1; j < nums.length; j ++){
                sum += nums[j];
                if (sum >= lower && sum <= upper){
                    count ++;
                }
            }
        }
        return count;
    }
    // 对算法进行优化
    // TODO 前缀数组+归并排序
    public int countRangeSum2(int[] nums, int lower, int upper) {
        // 首先构建前缀数据
        long sum = 0;
        // 构建前缀数组，前缀数组比原数组多一个
        long[] sumNum = new long[nums.length + 1];
        for (int i = 0; i < nums.length; i ++){
            sum += nums[i];
            sumNum[i + 1] = sum;
        }
        return countSort(sumNum, lower, upper, 0, sumNum.length - 1);
    }
    // 构建归并排序方法，并记数
    public int countSort(long[] sumNum, int lower, int upper, int left, int right) {
        if (left == right) return 0;
        else {
            // 首先需要归并排序
            int mid = (left + right) / 2;
            int leftNum = countSort(sumNum, lower, upper, left, mid);
            int rightNum = countSort(sumNum, lower, upper, mid + 1, right);

            int ret = leftNum + rightNum;
            // 左侧索引
            int leftIndex = left;
            // 移动索引
            int postion = mid + 1;
            // 右侧索引
            int rightIndex = mid + 1;
            // 对左侧进行遍历
            while (leftIndex < mid){
                // 当移动索引小于右侧边界,并且右侧position处的值 - 左侧leftIndex的值 < 左侧边界，想当于找到的左边界>= lower
                while (postion < right && sumNum[postion] - sumNum[leftIndex] < lower){
                    // 移动索引进行右移动，这里需要注意的是，左右为升序数组
                    postion ++;
                }
                // 这里想当于找到索引的右边界
                while (rightIndex < right && sumNum[rightIndex] - sumNum[leftIndex] <= upper){
                    rightIndex ++;
                }
                ret += rightIndex - postion;
                leftIndex ++;
            }
            // TODO 对数组进行合并,这里是归并排序的核心方法
            // 定义临时数组
            int[] sorted = new int[right - left + 1];
            // 左侧index 和 右侧 index
            int p1 = left, p2 = mid + 1;
            // 临时索引
            int p = 0;
            while (p1 <= mid || p2 <= right) {
                // 左侧遍历完
                if (p1 > mid) {
                    sorted[p++] = (int) sumNum[p2++];
                }
                // 右侧遍历完
                else if (p2 > right) {
                    sorted[p++] = (int) sumNum[p1++];
                } else {
                    if (sumNum[p1] < sumNum[p2]) {
                        sorted[p++] = (int) sumNum[p1++];
                    } else {
                        sorted[p++] = (int) sumNum[p2++];
                    }
                }
            }
            for (int j = 0; j < sorted.length; j++) {
                sumNum[left + j] = sorted[j];
            }
            return ret;
        }
    }

    /**
     * 现在有一个尺寸为 width * height 的矩阵 M，矩阵中的每个单元格的值不是 0 就是 1。
     *  而且矩阵 M 中每个大小为 sideLength * sideLength 的 正方形 子阵中，1 的数量不得超过 maxOnes。
     *  请你设计一个算法，计算矩阵中最多可以有多少个 1。
     *
     *  示例 1：
     *  输入：width = 3, height = 3, sideLength = 2, maxOnes = 1
     * 输出：4
     * 解释：
     * 题目要求：在一个 3*3 的矩阵中，每一个 2*2 的子阵中的 1 的数目不超过 1 个。
     * 最好的解决方案中，矩阵 M 里最多可以有 4 个 1，如下所示：
     * [1,0,1]
     * [0,0,0]
     * [1,0,1]
     *
     *  示例 2：
     *  输入：width = 3, height = 3, sideLength = 2, maxOnes = 2
     * 输出：6
     * 解释：
     * [1,0,1]
     * [1,0,1]
     * [1,0,1]
     *
     *  提示：
     *  1 <= width, height <= 100
     *  1 <= sideLength <= width, height
     *  0 <= maxOnes <= sideLength * sideLength
     *
     *  Related Topics 排序 数学
     */
    public static int maximumNumberOfOnes(int width, int height, int sideLength, int maxOnes) {
        int ans = 0;
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int i = 0; i < sideLength; i ++){
            for (int j = 0; j < sideLength; j ++){
                int num = 1;
                num *= (width - 1 - i) / sideLength + 1;
                num *= (height - 1 - j) / sideLength + 1;
                queue.add(num);
                if (queue.size() > maxOnes) queue.poll();
            }
        }
        while (!queue.isEmpty()) {
            ans += queue.poll();
        }
        return ans;
    }

    /**
     * 给定一个整数数组，编写一个函数，找出索引m和n，只要将索引区间[m,n]的元素排好序，整个数组就是有序的。
     * 注意：n-m尽量最小，也就是说，找出符合条件的最短
     * 序列。函数返回值为[m,n]，若不存在这样的m和n（例如整个数组是有序的），请返回[-1,-1]。
     *  示例：
     *  输入： [1,2,4,7,10,11,7,12,6,7,16,18,19]
     * 输出： [3,9]
     *
     *  提示：
     *  0 <= len(array) <= 1000000
     *  Related Topics 排序 数组
     */
    public int[] subSort(int[] array) {
        // 将数组克隆一份
        int[] arr = array.clone();
        // 对克隆数组进行排序
        Arrays.sort(arr);
        int left = -1;
        int right = -1;
        for (int i = 0; i < array.length; i ++){
            if (arr[i] != array[i]){
                // 当第一个不等于的i出现，为左边界
                if (left == -1) left = i;
                // 找到最后一个不等于的i，为右边界
                right = i;
            }
        }
        return new int[]{left, right};
    }

    /**
     * 最大的团队表现值
     * 公司有编号为 1 到 n 的 n 个工程师，给你两个数组 speed 和 efficiency ，其中 speed[i] 和 efficiency[i] 分
     * 别代表第 i 位工程师的速度和效率。请你返回由最多 k 个工程师组成的 最大团队表现值 ，由于答案可能很大，
     * 请你返回结果对 10^9 + 7 取余后的结果。
     *  团队表现值 的定义为：一个团队中「所有工程师速度的和」乘以他们「效率值中的最小值」。
     *
     *  示例 1：
     *  输入：n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 2
     * 输出：60
     * 解释：
     * 我们选择工程师 2（speed=10 且 efficiency=4）和工程师 5（speed=5 且 efficiency=7）。他们的团队表现值为
     * performance = (10 + 5) * min(4, 7) = 60 。
     *
     *  示例 2：
     *  输入：n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 3
     * 输出：68
     * 解释：
     * 此示例与第一个示例相同，除了 k = 3 。我们可以选择工程师 1 ，工程师 2 和工程师 5 得到最大的团队表现值。表现值为 performance =
     * (2 + 10 + 5) * min(5, 4, 7) = 68 。
     *
     *  示例 3：
     *  输入：n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 4
     * 输出：72
     *
     *  提示：
     *  1 <= n <= 10^5
     *  speed.length == n
     *  efficiency.length == n
     *  1 <= speed[i] <= 10^5
     *  1 <= efficiency[i] <= 10^8
     *  1 <= k <= n
     *
     *  Related Topics 贪心算法 排序
     */
    public static int maxPerformance(int n, int[] speed, int[] efficiency, int k) {

        // TODO 需要定一个元素，变一个元素
        // 先对工程师按效率从大到小排序，然后根据这个顺序选择工程师同时计算表现值
        // 由于是根据效率从大到小排序的，因此计算表现值的效率只会小于或等于上次计算的表现值，而速度和可能大于或小于或等于上次表现值
        Queue<int[]> queueEfficiencyMax = new PriorityQueue<>((o1, o2) -> o2[1] - o1[1]);
        Queue<Integer> speedMinHeap = new PriorityQueue<>();
        for (int i = 0; i < n; i ++){
            queueEfficiencyMax.offer(new int[]{speed[i], efficiency[i]});
        }
        long speeds = 0, res = 0;
        for (int i = 0; i < n; i ++){
            int[] enginer = queueEfficiencyMax.poll();
            speeds += enginer[0];
            speeds -= i >= k? speedMinHeap.poll() : 0;
            res = Math.max(res, speeds * enginer[1]);
        }

        return (int)(res % 1000000007);
    }
    //变换
    public static int maxPerformance2(int n, int[] speed, int[] efficiency, int k) {
        // TODO 思路：按照效率进行降序排序，每个人作为最低效率时，在其左侧找出至多K - 1个最大速度即可(再加上这个人的速度组成K个)，这一过程可以用堆，时间复杂度O(nlg(k-1))
        //
        // 根据n定义二维数组
        int[][] temp = new int[n][2];
        // 根据 i，将速度和效率放到二维数组中
        for (int i = 0; i < n; i ++){
            temp[i][0] = speed[i];
            temp[i][1] = efficiency[i];
        }
        // 对二维数组根据效率进行排队,从大到小
        Arrays.sort(temp, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o2[1] - o1[1];
            }
        });
        // 定义优先队列，根据自然数顺序自动排序
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        // sum 速度的和
        // res 速度和效率的最大值
        long res = 0, sum = 0;
        for (int i = 0; i < n; i ++){
            // 当队列长度大于k-1时，要弹出顶部，使队列保持这k个元素
            if(queue.size() > k - 1){
                sum -= queue.poll();
            }
            // res 的值是枚举了每一个的
            res = Math.max(res, (sum + temp[i][0]) * temp[i][1]);
            queue.add(temp[i][0]);
            sum += temp[i][0];
        }
        return (int)(res % ((int)1e9 + 7));
    }

    /**
     * 排序链表
     * 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
     *  进阶：
     *  你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
     *
     *  示例 1：
     * 输入：head = [4,2,1,3]
     * 输出：[1,2,3,4]
     *
     *  示例 2：
     * 输入：head = [-1,5,3,4,0]
     * 输出：[-1,0,3,4,5]
     *
     *  示例 3：
     * 输入：head = []
     * 输出：[]
     *
     *  提示：
     *  链表中节点的数目在范围 [0, 5 * 104] 内
     *  -105 <= Node.val <= 105
     *
     *  Related Topics 排序 链表
     */
    // Definition for singly-linked list.
    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
    // 通过对链表进行归并排序
    public ListNode sortList(ListNode head) {

        return mergeSort(head);
    }
    // 归并排序
    public ListNode mergeSort(ListNode head){
        // 如果没有节点或者只有一个节点，无需排序，直接返回
        if (head == null || head.next == null) return head;
        // 找到链表的中间节点,这里定义了快慢指针，快指针是慢指针的两倍，当快指针走到头，慢指针到达中间位置，从而找到中间节点
        ListNode fast = head.next.next, slow = head;
        while (fast != null && slow.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        // 慢指针右侧,获取到了
        ListNode rightNode = mergeSort(slow.next);
        // 慢指针右侧设置为null，获取到左半边listNode
        slow.next = null;
        ListNode leftNode = mergeSort(head);
        // 对左右链表进行合并
        return mergeList(leftNode, rightNode);
    }
    // 合并链表
    private ListNode mergeList(ListNode leftNode,ListNode rightNode){
        // 临时头节点
        ListNode tmpHead=new ListNode(-1);
        ListNode p=tmpHead;
        while (leftNode != null && rightNode != null){
            // 当左侧值小于右侧值，将小的节点放入临时节点
            if (leftNode.val < rightNode.val){
                p.next = leftNode;
                leftNode = leftNode.next;
            }else {
                p.next = rightNode;
                rightNode = rightNode.next;
            }
            p = p.next;
        }
        // 当存在一个为空的情况，需要将剩余的节点追加到临时listNode中
        p.next = leftNode == null ? rightNode : leftNode;
        return tmpHead.next;
    }

    /**
     * 插入区间
     * 给出一个无重叠的 ，按照区间起始端点排序的区间列表。
     *
     *  在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。
     *
     *  示例 1：
     *  输入：intervals = [[1,3],[6,9]], newInterval = [2,5]
     * 输出：[[1,5],[6,9]]
     *
     *  示例 2：
     *  输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
     * 输出：[[1,2],[3,10],[12,16]]
     * 解释：这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。
     *
     *  注意：输入类型已在 2019 年 4 月 15 日更改。请重置为默认代码定义以获取新的方法签名。
     *  Related Topics 排序 数组
     */
    public int[][] insert(int[][] intervals, int[] newInterval) {
        // 边界条件判断
        if (intervals.length == 0) return new int[][]{newInterval};
        // 结果list集合
        List<int[]> list = new ArrayList<>();
        // 左边界
        int left = 0;
        // 右边界
        int right = intervals.length - 1;
        // 左侧不重合区间
        while (left < intervals.length && intervals[left][0] < newInterval[0]){
            list.add(intervals[left]);
            left ++;
        }
        // 右侧不重合区间
        while (right > 0 && intervals[right][1] > newInterval[1]){
            list.add(left, intervals[right]);
            right --;
        }
        // 合并重合区间
        int[] newArr = new int[2];
        newArr[0] = left > intervals.length ? newInterval[0] : Math.min(intervals[left][0], newInterval[0]);
        newArr[1] = right < 0 ? newInterval[1] : Math.max(intervals[right][1], newInterval[1]);

        list.add(left, newArr);

        int[][] res = new int[list.size()][2];
        for (int i = 0; i < list.size(); i ++){
            res[i] = list.get(i);
        }
        return res;
    }

    public int[][] insert2(int[][] intervals, int[] newInterval) {
        List<int[]> list = new ArrayList<>();
        int len = intervals.length;
        int index = 0;
        // 左侧未重合部分
        while (index < len && intervals[index][1] < newInterval[0]){
            list.add(intervals[index]);
            index ++;
        }
        // 出现重叠部分
        while (index < len && intervals[index][0] <= newInterval[1]){
            newInterval[0] = Math.min(newInterval[0], intervals[index][0]);
            newInterval[1] = Math.max(newInterval[1], intervals[index][1]);
            index ++;
        }
        list.add(newInterval);
        while (index < len){
            list.add(intervals[index]);
            index ++;
        }
        int[][] array=new int[list.size()][2];
        for(int i=0;i<list.size();i++){
            array[i]=list.get(i);
        }
        return array;
    }





    public static void main(String[] args) {
//        maximumNumberOfOnes(3, 3, 2, 1);
        int n = 6;
        int[] speed = {2,10,3,1,5,8};
        int[] efficiency = {5,4,3,9,7,2};
        int k = 3;
        maxPerformance(n, speed, efficiency, k);
    }




}
